1. Field of Invention The present invention relates generally to the resolution associated with a system clock in a computing system. More specifically, the present invention relates to a system which enables arbitrary resolution interval timeouts to be implemented.
2. Description of the Related Art
Computing systems are clock-driven systems in that a clock, i.e., a hardware clock, tracks time and sends out signals at specific intervals to cause actions within the computing systems. Operations performed on a processor of a computing system are typically only performed when initiated by a clock signal.
Many computing systems have a clock interrupt that fires at a constant rate, and is used to schedule system resources, perform accounting, and execute callouts, i.e., routines that execute on a given clock tick. A time increment may be specified within the system to implement a callout-based timer using the clock ticks. That is, a resolution of clock ticks and, hence, timeouts may be specified.
A system clock typically has multiple clients which use the system clock to implement a timer. By way of example, kernel timeout facilities are generally implemented as clients of a system clock. Such facilities are often insufficient for real-time demands. As will be appreciated by those skilled in the art, in addition to being characterized by a high latency as well as jitter, time out facilities based on a single system clock are also characterized by limited resolution, namely, that of the system clock.
FIG. 1 is a diagrammatic representation of the interaction between drivers for devices, a system clock, and a central processing unit (CPU). A computing system 102 includes a CPU 110 and various devices 120 that may include, but are not limited to, various computer peripherals, e.g., printers and monitors. Devices 120 have associated device drivers 130 which enable devices 120 to interface with CPU 110. Device drivers 130 are typically in communication with a timeout interface 140 that enables callouts to be executed. Timeout interface 140 communicates with a system clock 150 that communicates directly with CPU 110. As shown, within computing system 102, devices 120 are effectively clients of system clock 150.
The resolution of timeouts is typically limited by the resolution of the system clock of a computing system, e.g., system clock 150 of computing system 102. The system clock resolution generally defaults to a resolution of ten milliseconds (ms), or one hundred interrupts per second. The granularity of timeouts with a ten millisecond resolution, or a one hundred Hertz (Hz) rate, is often unacceptable for realtime applications.
Computing system 102 also generally includes other devices that require interval-based timers. For instance, clients 160 and 170 use interval-based timers. Clients 160 and 170, in addition to clients 180 and 185, use a realtime timeout interface 190 to interface with system clock 150. Realtime timeout interface 190 enables real time callouts to be made, and execute at a relatively high priority, while timeout interface 140 enables non-realtime callouts to be made from, for example, a thread that is running at the maximum priority of all system scheduling classes.
When a device, e.g., a peripheral device, that is supported by the computing system requires an internal timer at a different rate, such as a rate which is less than the default system clock resolution of ten milliseconds, the system clock rate may be tuned to meet the resolution required by the peripheral device. For instance, the system clock rate on a configurable system may be tuned to 1,000 Hz allowing for a one millisecond resolution.
While tuning the system clock may enable different interval timer rates to be supported, such tuning often results in undesirable side effects. By way of example, executing a clock interrupt up to ten times as often as typical may decrease overall system performance because of the increased interrupt load. The typically high level of a clock interrupt, coupled with the increased rate of timeouts may significantly increase interrupt latency, in addition to further decreasing system performance, as will be appreciated by those skilled in the art. Further, a one millisecond resolution is often still too coarse for many applications.
In many computing systems, devices with different interval timer requirements must often be supported by a single system clock. By way of example, a system may need to support a device with a timer rate of 433 Hz as well as a device with a timer rate of 60 Hz. In order to support more than one timer rate with the system clock, the system clock may be tuned, e.g., manually tuned, such that substantially arbitrary clock rates may be supported. As discussed above, increasing the timeout resolution may enable different devices to be supported. However, tuning the system clock generally does not allow timeouts for the different devices to be accurately set at a fine resolution. Tuning the system clock to a faster interrupt rate also results in increased latency and jitter within a computing system that supports multiple devices.
Some computing systems implement a timestamp-compare register for use with a timestamp register to enable arbitrary resolution timeouts, or interrupts. A timestamp register is typically a register which increments once per CPU cycle. For example, a timestamp register may increment 450 million times per second in a 450 MegaHertz (MHz) system. A timestamp-compare register is used to specify a time when a particular device requires a clock interrupt. When a comparison of the contents of the timestamp-compare register are found to equal the contents of a timestamp register, an interrupt is generated. Using a timestamp-compare register offers more flexibility than an internal-based piece of clock hardware, as the use of a timestamp-compare register generally does not force an operating system to choose a single interval. However, the use of a timestamp-compare register does not allow for dynamic time intervals to be implemented. Instead, the use of a timestamp-compare register typically implements static time intervals.
Therefore, what is desired is an efficient method for generating system timeouts or interrupts. That is, what is needed is a method for generating arbitrary resolution timeouts without incurring significant performance penalties, latency, or jitter.
The present invention relates to a system for enabling timeouts with arbitrary resolutions to be implemented which does not induce significant latency and jitter. According to one aspect of the present invention, a method for enabling a device driver to communicate with a processor in a computing system includes exchanging information between the device driver and a clock system, and exchanging information between the clock system and a cyclic system. Information is also exchanged between the cyclic system and the processor. Although the clock system indirectly exchanges information with the processor, the clock system does not directly exchange information with the processor.
The use of a clock system which does not exchange information directly with a processor and, instead, communicates with the processor through a cyclic system enables arbitrary timeouts to be implemented. Hence, access by clients to a processor may be unified. Further, by maintaining the clock system as a client of the cyclic system, legacy information associated with the overall computing system may be maintained.
In one embodiment, the clock system includes a callout system and a system clock, and exchanging information between the device driver and the clock system includes exchanging information between the system clock and the callout system, and exchanging information between the callout system and the device driver. In such an embodiment, the cyclic system includes an associated heap with a plurality of cyclics, and the method includes processing the heap to identify a cyclic that has an unexpired expiration time.
In another embodiment, the method may involve processing a lock-free software interrupt in a lock-free manner. Processing the software interrupt may include calling a handler associated with a cyclic. In still another embodiment, the method includes generating a clock interrupt using the cyclic system and the clock system.
According to another aspect of the present invention, a computing system that enables arbitrary resolution timeouts to be generated includes a first central processing unit and a memory, which includes a data structure, that is in communication with the first central processing unit. A cyclic system communicates with the first central processing unit and is arranged to maintain a heap of cyclics and to identify expiration times associated with the cyclics. A clock system of the computing system is in substantially direct communication with the cyclic system, and is not arranged to communicate directly with the first central processing unit. The computing system also includes a device driver that is arranged to communicate with the clock system. In one embodiment, the data structure is a producer/consumer buffer which is arranged to reference the cyclics by effectively keeping track of pending cyclics.
In accordance with yet another aspect of the present invention, a computer-implemented method for responding to cyclic firing in a computing system with a system clock, a cyclic subsystem, and a central processing unit, includes comparing a current system time with an expiration time of a root cyclic. The current system time is obtained from the timestamp register, and the root cyclic is associated with a heap or a priority queue of the cyclic subsystem. The method also includes determining when the expiration time has passed, and reprogramming the interrupt source to fire at the expiration time when it is determined that the expiration time has not passed. In one embodiment, the method further requires obtaining a new expiration time when it is determined that the expiration time has passed, performing a downheap process on the heap to obtain a new root cyclic when it is determined that the expiration time has passed, and comparing a new current time with the new expiration time.
In accordance with still another aspect of the present invention, a computer-implemented method for enabling a device driver to communicate with a processor associated with a computing system includes exchanging information between a clock system and a cyclic system, as well as exchanging information between the cyclic system and the processor. The clock system does not directly exchange information with the processor. The method also includes implementing arbitrary resolution timeouts using the clock system and the cyclic system such that the arbitrary resolution timeouts are specifically implemented using a timestamp-compare register of the computing system. The arbitrary resolution timeouts are arranged to be used by the device driver.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.